package com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序;

import com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.归并排序.MergeSort;
import com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.快速排序.QuickSortV1;
import com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.快速排序.QuickSortV2;
import com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.插入排序.InsertionSort;
import com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.桶排序.BucketSortV1;
import com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.选择排序.SelectionSort;

import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author Baixiaowen
 */
public class SortTests {

    public static void main(String[] args) {
        // 插入排序
        sortTest(InsertionSort.class, 100_000);
        // 选择排序
        sortTest(SelectionSort.class, 100_000);
        // 冒泡排序 - 通常不用
        // 冒泡排序相对选择排序会慢很多，因为冒泡排序的写操作要比选择排序的写操作多很多
//        sortTest(BubbleSort.class, 100_000);
        // 归并排序
        sortTest(MergeSort.class, 100_000);
        // 快速排序 版本1
        sortTest(QuickSortV1.class, 100_000);
        // 快速排序 版本2
        sortTest(QuickSortV2.class, 100_000);

        // 通排序 排序100w个 0 - 99 之间的数据
        test_bucketSort();

    }

    public static void test_bucketSort(){
        BucketSortV1 bucketSort = new BucketSortV1();
        ArrayList<Integer> l = new ArrayList<>();

        for(int i = 0; i < 1000000; i++) {
            l.add((int) (Math.random() * 100));
        }
        long start = System.currentTimeMillis();
        List<Integer> A = bucketSort.sort(l);
        System.out.println("time:" + (System.currentTimeMillis() - start));
        assertSorted(A);
    }
    

    public static void sortTest(Class cls, int N) {

        try{
            Constructor constructor = cls.getConstructor();
            Object rawInst = constructor.newInstance();
            long start = System.currentTimeMillis();
            if (rawInst instanceof IIMutableSorter) {
                List<Integer> A = gen(N);
                IIMutableSorter inst = (IIMutableSorter) rawInst;
                A = inst.sort(A);
                System.err.println("time usages: " + (System.currentTimeMillis() - start));
                assertSorted(A);
            } else if (rawInst instanceof IMutableSorter) {
                int[] A = gen(N).stream().mapToInt(x -> x).toArray();
                IMutableSorter inst = (IMutableSorter) rawInst;
                inst.sort(A);
                System.err.println("time usages: " + (System.currentTimeMillis() - start));
                assertSorted(A);
            }
        } catch (InstantiationException e) {
            e.printStackTrace();
        } catch (InvocationTargetException e) {
            e.printStackTrace();
        } catch (NoSuchMethodException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        }

    }

    static void assertSorted(int[] A) {
        assertSorted(Arrays.stream(A).boxed().collect(Collectors.toList()));
    }

    static void assertSorted(List<Integer> A) {
        Integer o = Integer.MIN_VALUE;
        for (Integer i : A) {
            if (o > i) {
                System.err.println(A.toString());
                try {
                    throw new Exception("Array not in sorted order");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            o = i;
        }
    }

    static List<Integer> gen(int n){
        List<Integer> A = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            A.add((int) (Math.random() * n));
        }
        return A;
    }


}
